HSH_HashTable is a simple replacement for RB built-in collection class. As of the time this is being written, the RB collection class still uses a rather slow, apparently brute-force data retrieval mechanism. HSH_HashTable implements faster acess at cost of space. It uses multiplicative hashing on a static object array to retrieve an object with a given key.
However, this implementation has a fairly simple hash-collision management strategy. It always uses a list to store objects and simply appends collided objects to the list, searching the object list sequentially when a key collision appears. As for each object stored an individual list is created, and each key is stored as well, the implementation is rather memory-consuming.
The package contains three classes: hsh_HashObject, hsh_HashEntry, hsh_HashTable, and one module: hsh_Constants.
II. Usage
To use a hashtable, drag all of the three classes and the module onto your project window. To create a new hsh_HashTable with a maximum of 1000 entries, use:
Dim h as hsh_HashTable
h = new hsh_HashTable(1000)
the constructor takes the expected maximum number of items in the table.
To add an object to the table, the object must be an instance of the class interface hsh_HashObject. In your own custom class definition, you therefore have to add hsh_HashObject to the interface property in the properties window of the class. An object is then added by
add obj as hsh_HashObject, key as String
an object is retrieved by
get( key as String) as hsh_HashObject
For example, to retrieve an object with key “john smith” of class someClass (which is also an hsh_HashObject), you'd use:
Dim myObj as someClass
myObj = someClass( hashtable.get("john smith"))
The get() function returns NIL if the object hasn't been stored by the given key. You usually will have to typecast the object back to the original class like shown in the above sample.
III. Methods
Here, we only describe public methods that are recommended for use. You should neither call hash(), cloneEntry(), nor manipulate hsh_HashEntry objects directly, unless know exactly what you do.
1. Constructors
hsh_HashTable( size as Integer )
create a new hash table as big as given by size. The number of elements may actually grow bigger than size, but then the access to individial items may slow down significantly. HSH_HashTables are static, you cannot resize them later.
hsh_HashTable( source as hsh_HashTable, dummy as integer )
creates a clone of an existing hsh_HashTable object (“source”). Note that all objects added to “source” are copies by reference, objects are not cloned. The parameter “dummy” is useless, but necessary to outwit RB’s silly compiler who doesn’t understand overloaded constructors with the same parameter count (Bug base #0935; this may have been fixed in more recent versions of RB but the constructor is kept for downwards compatibility).
2. Accessor Methods
get( key as String ) as hsh_HashObject
get( i as Integer ) as hsh_HashObject
item( key as String ) as hsh_HashObject
item( i as Integer ) as hsh_HashObject
return an item by a given key or by a given index (1-based). Please note that, differing from RB Collections, the order of the objects in the table is unspecified and that accessing an item by index i is very slow! If you want to dump/display/save the whole table, you should use the method copyIntoArray(), see below; but if you need random access by index i, you would probably better use an array!
key( i as Integer ) as String
return i-th key in the table. 1-based and the order is unspecified.
known( key as string ) as Boolean
return true if the table contains an entry for key, false otherwise
3. Assignment Methods
add( obj as hsh_HashObject, key as String )
add obj to the table, using key as hash
addIfUnknown( obj as hsh_HashObject, key as String ) as Boolean
replaceIfKnown( obj as hsh_HashObject, key as String ) as Boolean
Two special variants of add(); you rarely need them, but then they are much faster than testing known() first and subsequently calling add().
— addifUnknown(): If the table contains no entry for key, a new entry is added and the result is true; else, the table is not changed and the result is false.
— replaceIfKnown(): If the table already contains an entry for key, its value is replaced and the result is true; else, the table is not changed and the result is false.
4. Destructor Methods
remove( key as String )
remove the object specified by key. Does nothing if there's no object with key.
removeIfKnown( key as String ) as Boolean
A special variant of remove(), cf. replaceIfKnown() above. If the table contains an entry for key(), the entry is removed and the result is true; else, the table is not changed and the result is false.
6. Size Methods
capacity() as Integer
return the nominal size of the table, regardless of the acutal number of stored items
count() as Integer
return the actual number of items stored in the table
7. Dump Methods
copyIntoArray( items() as hsh_HashObject, keys() as string )
copyItemsIntoArray( items() as hsh_HashObject )
copyKeysIntoArray( keys() as string )
These methods copy all objects/keys into an array. The order of the objects/keys is unspecified, but if you call copyIntoArray(), items and keys should match exactly. Use these methods if you need to display or save the contents of your hash table; they are not fast, but much faster than repetitive calls to get(i) and key(i).
dumpDistribution( target() as String )
Use this method to study the distribution of objects over the hash table. See the Sample project for an example.
IV. Hints
1. Build your project before you test performance!
In a compiled application, RB code runs faster than in a “debug build” in the IDE. If you want to compare the speed of HSH_HashTable with the speed of the RB collection class, you should build your project first.
2. Collection or HSH_HashTable?
If you only need to add a few items per hash table object, you should probably stay with RB’s built-in collection class: HSH_HashTable is faster, but requires some overhead which doesn't pay until there is a certain number of entries. Use the “Benchmark” feature of the Sample project to explore the limits.
3. How large should a hash table be?
As mentioned earlier, you could add 100 items to a table initialized for a maximum of 10 entries — but access to entries of that table would be rather slow ;-). To achieve best performance, you should initialize the table for even more entries than you will ever add to it; we have not tested HSH_HashTable extensively, but an old rule of thumb is that you should fill a hash table only to about 80% of its nominal capacity.
V. Limitations & Known Bugs
A KEY STRING MAY ONLY BE UP TO 32 CHARACTERS IN LENGTH. Any additional characters are not used for hash calculation.
You currently cannot add or remove an object by index, and this functionality is very unlikely to be added in future: it would be too slow. If you need access by index, you don't need a hash-table but an ordinary array.
The classes have not been tested extensively yet, so please write bug reports and suggest improvements; see “Contact” below.
Feel free to use the classes as basis to your own hashtable implementations, and if you develop a nice improved hashtable class, please make it available to others so everyone can benefit of it.
The package is provided “as is” without any warranty.
VI. Credits & Contact
Many thanks to pantarei for his bug reports and toughtful commentaries. :-)
Updates of the HSH_HashTable package can always be found at:
http://www.snafu.de/~erich/realbasic/rb.html
Send questions and bug reports to: <erich@snafu.de>
